/*
 * @lc app=leetcode.cn id=621 lang=c
 *
 * [621] 任务调度器
 */

// @lc code=start


int leastInterval(char* tasks, int tasksSize, int n){
    int freq[26];
    memset(freq, 0, sizeof(freq));
    for (int i = 0; i < tasksSize; ++i)
    {
        ++freq[tasks[i] - 'A'];
    }

    int m = 0;
    int nextValid[26], rest[26];
    for (int i = 0; i < 26; ++i)
    {
        if (freq[i] > 0) {
            nextValid[m] = 1;
            rest[m++] = freq[i];
        }
    }

    int time = 0;
    for (int i = 0; i < tasksSize; ++i) {
        ++time;
        int minValidTime = INT_MAX;
        for (int j = 0; j < m; ++j) {
            if (rest[j]) {
                minValidTime = fmin(minValidTime, nextValid[j]);
            }
        }
        time = fmax(time, minValidTime);

        int best = -1;
        for (int j = 0; j < m; ++j) {
            if (rest[j] && nextValid[j] <= time) {
                if (best == -1 || rest[j] > rest[best]) {
                    best = j;
                }
            }
        }
        nextValid[best] = time + n + 1;
        --rest[best];
    }
    return time;
}
// @lc code=end

